package com.backpack;

import java.util.Arrays;

/**
 * 输入：nums = [1,2,3], target = 4
 * 输出：7
 * 解释：
 * 所有可能的组合为：
 * (1, 1, 1, 1)
 * (1, 1, 2)
 * (1, 2, 1)
 * (1, 3)
 * (2, 1, 1)
 * (2, 2)
 * (3, 1)
 * 请注意，顺序不同的序列被视作不同的组合。
 */
public class CombinationSumIV0112_377 {
    public int combinationSum4(int[] nums, int target) {
        //完全背包问题，元素组合有多少方式
        //dp[i]含义 表示容量和为i 有dp[i]种元素组合方式
        int[] dp = new int[target + 1];

        //初始化
        dp[0] = 1;

        //遍历公式： dp[j] += dp[j-nums[i]];
        //遍历顺序：元素组合问题，应该先遍历背包容量（正序），再遍历物品元素（正序）
        for (int i = 1; i <= target; i++) { //背包容量
            for (int j = 0; j < nums.length; j++) { //物品
                if((i-nums[j]) >=0) dp[i] += dp[i-nums[j]];
            }
        }
        return dp[target];
    }
}
